A discrete Fourier transform (DFT) is a mathematical transform that converts one function from one domain to another. Specifically, a DFT is a frequency representation of the original function, the original function generally being a signal in the time domain. The input to a DFT is a finite list of equally spaced samples of a continuous signal. DFTs may be implemented in both computer algorithms executed by a general- or special-purpose processors, or directly in hardware.
A sliding discrete Fourier transform (SDFT) is a popular algorithm used in nonparametric spectrum estimation when only a few frequency bins of an M-point DFT are of interest. Although the classical SDFT algorithm is generally computationally efficient, its recursive structure suffers from accumulation and rounding errors, which can lead to instabilities or inaccurate output. One prior approach is to use a modulated SDFT algorithm, which is generally stable without sacrificing accuracy.
Conventional SDFT's may be tailored to compute a DFT on a sample-by-sample basis. However, such techniques are not generally computationally efficient when programmable output rate is needed. Some approaches have proposed a hopping SDFT algorithm for situations where computational downsampling is needed.
The typical method for spectrum analysis in digital signal processors (DSP) is the discrete Fourier transform (DFT). The DFT converts a continuous signal in a first domain (e.g., time domain) into a frequency domain representation for a discrete set of frequencies. Rather than looking for the frequency content of the continuous signal at all possible frequencies, the DFT divides up the frequency spectrum of the signal into a number of frequency hands, referred to as bins.
In some applications, however, spectrum analysis is only necessary over a subset of M frequencies of an M-point DFT. One algorithm useful in such applications is the sliding discrete Fourier transform (SDFT). The SDFT performs an M-point DFT on time samples within a sliding-window function. The SDFT computes an M-point DFT for samples within a first window position, shifts the window by one sample, and then computes another M-point DFT for samples within the new window position. Each new DFT is efficiently computed directly from the results of the previous DFT. That is, the kth frequency bin of an M-point DFT at time index n for input signal x is defined by
                              X          n          k                =                              ∑                          m              =              0                                      M              -              1                                ⁢                                    x                              q                +                m                                      ⁢                          W              M                              -                km                                                                        (        1        )            where q=n−M+1,0≤k≤M−1, and the complex exponential factor WM=ej2π/M (also known as a twiddle factor).
As noted above, a sliding DFT calculates the DFT recursively. A recursive equivalent of equation (1) is given byXnk=WMk(Xn−1k−xn−M+xn).  (2)
FIG. 1 illustrates an example circuit representation 100 implementing the conventional SDFT described above in equation (2). The structure of DFT 100 includes a comb stage 120 including a first delay block 102 and a first adder, or add block 104, and an integrator stage 130 including a second add block 106, a second delay block 108, and a multiplier 110. In various embodiments, the circuit 100 may include multiple integrator stages 130, each configured to extract a specific frequency bin of an M-point DFT.
The first delay block 102 of the comb stage 120 generates a delayed sample xn−M. The delayed sample xn−M is subtracted from the current sample xn by the first add block 104. The output of the first add block 104 is provided to the integrator stage 130. In the integrator stage 130 at the second add block 106, the previous accumulation result Xn−1k is added to the current sample xn−xn−M. The multiplier 110 as a first input that receives the output of second add block 106 the output from the second add block 106, and a second input that receives a twiddle factor WMk. Multiplier 110 multiplies these two inputs to generate the weighted-sum output representing the DFT of the kth bin.
The second delay block 108 delays this output and feeds it back to second add block 106. As received by second add block 106 it is the previous result Xn−1k and it may be added to the modified, now-current sample outputted from the first add block 104.
Although computationally efficient, the SDFT has several drawbacks that impact its effectiveness in different applications. The recursive structure of the conventional SDFT results in only a marginally stable output because it has a z-domain pole located on the unit circle at z=WMk. Hence, it is only marginally stable in finite precision recursive calculations with accumulation, except at points when poles z=±1 or z=±j. As the twiddle factor for the kth bin (WMk) is typically imprecise, any errors accumulate over time, leading to potential instabilities in the output. This is particularly an issue in fixed-point implementations, such as implementations in circuitry, but is also present within floating-point applications. For example, in a processing device implementing SDFT 100, the accumulated error becomes exponentially large for infinite time (e.g., for a device that is turned on and runs for a long duration). Moreover, the SDFT functions on a sample-by-sample basis only. Each conventional SDFT output must be computed for each new input sample due to the recursive structure. If a new M-point DFT output needs to be computed only every R samples (R>1), the conventional SDFT loses computational efficiency. Thus, R-times decreased output rate requires the same amount of computations as the case with R=1.
One potential solution to the issues caused due to the recursive nature of the conventional SDFT is to multiply the samples by a modulated sequence (modulated twiddle factor) prior to entering the comb stage, referred to as a modulated SDFT, or mSDFT. The mSDFT shifts each specific bin of interest (Xk) to the k=0 index, and then calculates the new zero-frequency DFT bin (Y0) asXnk=Yn0=Yn−10−yn−M+yn,  (3)where yn=xnWM−km and yn−M=xn−mWM−k(m−M).
FIG. 2 illustrates an example circuit 200 implementing the mSDFT. The mSDFT 200 includes similar components as discussed above with respect to filter 100 of FIG. 1. In this example, mSDFT 200 includes a comb stage 220, which further includes a first delay block 202 and a first adder 204; and an integrator stage 230, which includes a second adder 206 and a second delay block 208. Unlike filter 100, the multiplier 210 of mSDFT 200 is located at the input of the filter 200, such that the input sample xn is multiplied by the modulated sequence WM−km to produce yn prior to entering the comb stage 220. By removing the complex multiplication of multiplier 210 from the recursive integrator section, the specific bin of interest for the calculation (Xk) is shifted to the k=0 index, for which WM0=1 (which guarantees a stable and accurate output of the recursive section). The rest of the mSDFT 200 operates in a similar fashion as discussed above with respect to SDFT 100, except that the operations are applied to the samples yn.
However, the mSDFT still poses several issues. First, the accuracy of spectrum estimation is limited due to support of only rectangular DFT windows. The complexity of more advanced windows grows faster than a linear function of window length. Second, the mSDFT still operates only on a sample-by-sample basis, without the ability to efficiently calculate the DFTs for programmable output rates R (R>1).